package com.felix.algorithms.sort;


import java.util.Arrays;

/**
 * QuickSort
 *
 * @author xuejinhua
 * @date 2018/10/16 15:47
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] list = new int[100];
        for (int i = 0; i < 100; i++) {
            list[i] = i;
        }
        System.out.println("************快速排序************");
        System.out.println("排序前：");
        display(list);
        list = shuffle(list);
        display(list);
        System.out.println("排序后：");
        long begin = System.currentTimeMillis();
        quickSort(list, 0, list.length - 1);
        display(list);
        System.out.println("quick sort cost time: " + (System.currentTimeMillis() - begin));
    }

    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            int point = (left + right) / 2;
            quickSort(list, left, point - 1);
            quickSort(list, point + 1, right);
        }
    }

    public static int[] shuffle(int[] array) {
        int i = array.length;
        while (i > 0) {
            int j = (int) Math.floor(Math.random() * i--);
            int temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        return array;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        if (list == null || list.length == 0) {
            return;
        }
        int temp = list[left];
        list[left] = list[right];
        list[right] = temp;
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        if (list != null && list.length > 0) {
            for (int num : list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
    }

}
